1. Technical Field
The present invention generally relates to three-dimensional imaging and, in particular, to a memory efficient shear-warp volume rendering method.
2. Background Description Shear-warp volume rendering algorithms transform a volume to an intermediate coordinate system, referred to as the xe2x80x9csheared object spacexe2x80x9d, in which voxel data can be projected efficiently. The transposed dataset having the set of slices most perpendicular to the viewing direction is projected in sheared object space, and then the resulting intermediate image is warped back from sheared object coordinates to image coordinates to produce the final output image.
Conventional shear-warp algorithms by Klein et al., Lacroute et al., Cameron et al., and so forth, transpose voxel data so that parallel slices can be sheared into an intermediate image. Two additional transposed copies of the voxel data are generated, usually during a pre-processing step, leading to triple redundancy of data in memory. The shear-warp algorithm of Klein et al., is described in xe2x80x9cA Prebuffer Algorithm for Instant Display of Volume Dataxe2x80x9d, Proceedings of SPIE (Architectures and Algorithms for Digital Image Processing), Vol. 596, pp. 54-58, 1985. The shear-warp algorithm of Lacroute et al. is described in xe2x80x9cFast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformxe2x80x9d, ACM SIGGRAPH Computer Graphics Proceedings, Annual Conferences Series, July, pp. 451-458, 1994. The shear-warp algorithm of Cameron et al., is described in xe2x80x9cRendering Volumetric Medial Image Data on a SIMD Architecture Computerxe2x80x9d, Proceedings of the Third Eurographics Workshop on Rendering, Bristol, UK, pp. 135-145, 1992.
Accordingly, it would be desirable and highly advantageous to have a shear-warp method that eliminates the two additional and redundant transposed datasets and that always traverses the original dataset in a slice-by-slice fashion, without having to generate transposed data.
The problems stated above, as well as other related problems of the prior art, are solved by the present invention, a memory efficient shear-warp method.
Advantageously, the method of the present invention produces results at least identical to existing shear-warp algorithms with respect to image rendering, but with the following advantages over the existing shear-warp algorithms. The pre-processing time to generate transposed slices is not needed. Moreover, the triple redundancy of allocated memory for transposed data is not needed. Further, it is not necessary to access memory addresses in transposed order (which also would require all the volume slices to be located in memory).
The method of the present invention has very low memory requirements since, for example, the original voxel data is preferably always accessed in a slice-by-slice fashion. Therefore, as long as the computer has enough memory to hold one slice of data, volumes with an unlimited number of slices can be rendered.
According to an embodiment of the present invention, a method for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume is provided, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, the method comprising the steps of: selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; and rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.
According to another embodiment of the present invention, a method is provided for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, said method comprising the steps of: selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; constructing a look-up table (LUT) having a plurality of entries for storing integer pixel locations of shear projection coordinates that represent sheared locations to be used in a sheared projection of the sample points onto an intermediate shear image buffer; and rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.
A method is also provided for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, the method comprising the steps of: determining a dominant axis of a viewing transformation chosen for generating an image of the three-dimensional volume; selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; factorizing a permuted viewing transformation to obtain shear and warp transformation matrices; computing a size of an intermediate shear image buffer in which all of the sample points will be projected; computing a set of shear projection coordinates that represent sheared locations to be used for a sheared projection of the sample points onto the intermediate shear image buffer, according to the shear transformation matrix; determining an optimal traversal order through the sample points, based on a first determination of whether each of the plurality of slices are to be traversed sequentially front-to-back or back-to-front, a second determination of whether the scan lines are to be traversed sequentially top to bottom or bottom to top, and a third determination of whether the scan lines are to be traversed sequentially from left to right or from right to left; traversing and projecting the sample points stored in each of the scan lines; warping a resulting shear image buffer onto the image, according to the shear transformation matrix.
According to still another aspect of the invention, a program storage device is provided, the device having a program executable by a computer for performing method steps for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, the method comprising the steps of: selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; and rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.
These and other aspects, features and advantages of the present invention will become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings.